﻿#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
namespace AbstractClass.Collections.Generic
{
    /// <summary>
    /// Represents a self-balancing <see cref="BinarySearchTree&lt;T&gt;"/>.
    /// It can search, insert, and delete in O(log n) time, where n is total number of elements in the tree.
    /// </summary>
    /// <typeparam name="T">The type of the data in the collection.</typeparam>
    public class RedBlackTree<T> : BinarySearchTree<T>
    {
        private readonly BinaryTreeNode<T> _sentinel;

        /// <summary>
        /// Initializes a new instance of the <see cref="RedBlackTree&lt;T&gt;"/> class.
        /// </summary>
        public RedBlackTree()
        {
            _sentinel = new BinaryTreeNode<T> {_Color = NodeColor.Black};
            _Root = _sentinel;
            _sentinel._Left = _sentinel;
            _sentinel._Right = _sentinel;
            _sentinel.Parent = _sentinel;
        }

        /// <summary>
        ///   Adds an item to the <see cref="RedBlackTree&lt;T&gt;"/>.
        /// </summary>
        /// <param name = "item">The object to add to the <see cref="RedBlackTree&lt;T&gt;"/>.
        /// </param>
        public override void Add(T item)
        {
            BinaryTreeNode<T> parent = null;

            if (_Root == null || _Root == _sentinel)
            {
                _Root = new BinaryTreeNode<T>
                            {_Color = NodeColor.Red, _Left = _sentinel, _Right = _sentinel, Value = item};
                Count++;
                return;
            }

            BinaryTreeNode<T> current = _Root;
            while (current != _sentinel)
            {
                int rc = Comparer.Compare(item, current.Value);
                if (rc == 0)
                {
                    return;
                }
                parent = current;
                current = (rc < 0) ? current._Left : current._Right;
            }

            var x = new BinaryTreeNode<T>
                        {
                            Parent = parent,
                            _Left = _sentinel,
                            _Right = _sentinel,
                            _Color = NodeColor.Red,
                            Value = item
                        };

            if (parent != null)
            {
                if (Comparer.Compare(item, parent.Value) < 0)
                {
                    parent._Left = x;
                }
                else
                {
                    parent._Right = x;
                }
            }
            else
            {
                _Root = x;
            }

            InsertFixup(x);
            Count++;
        }

        /// <summary>
        ///   Removes the first occurrence of a specific object from the <see cref="RedBlackTree&lt;T&gt;"/>.
        /// </summary>
        /// <param name="item">The object to remove from the <see cref="RedBlackTree&lt;T&gt;"/>.
        /// </param>
        /// <returns>
        ///   <c>true</c> if <paramref name="item" /> was successfully removed from the <see cref="RedBlackTree&lt;T&gt;"/>;
        /// 		otherwise, <c>false</c>. This method also returns <c>false</c> if <paramref name="item" /> is not found in the original
        /// 		<see cref="RedBlackTree&lt;T&gt;"/>.
        /// </returns>
        public override bool Remove(T item)
        {
            BinaryTreeNode<T> y;
            if (_Root == null)
            {
                return false;
            }

            BinaryTreeNode<T> z = Find(item);
            if (z == null)
            {
                return false;
            }

            if (z._Left == _sentinel || z._Right == _sentinel)
            {
                y = z;
            }
            else
            {
                y = z._Right;
                while (y._Left != _sentinel)
                {
                    y = y._Left;
                }
            }

            BinaryTreeNode<T> x = y._Left != _sentinel ? y._Left : y._Right;

            x.Parent = y.Parent;
            if (y.Parent != null && y.Parent != _sentinel)
            {
                if (y == ((BinaryTreeNode<T>) y.Parent)._Left)
                {
                    ((BinaryTreeNode<T>) y.Parent)._Left = x;
                }
                else
                {
                    ((BinaryTreeNode<T>) y.Parent)._Right = x;
                }
            }
            else
            {
                _Root = x;
            }

            if (y != z)
            {
                z.Value = y.Value;
            }

            if (y._Color == NodeColor.Black)
            {
                DeleteFixup(x);
            }
            Count--;
            return true;
        }

        private void RotateLeft(BinaryTreeNode<T> x)
        {
            BinaryTreeNode<T> y = x._Right;
            x._Right = y._Left;
            if (y._Left != _sentinel && y._Left != null)
            {
                y._Left.Parent = x;
            }

            if (y != _sentinel)
            {
                y.Parent = x.Parent;
            }

            if (x.Parent != null && x.Parent != _sentinel)
            {
                if (x == ((BinaryTreeNode<T>) x.Parent)._Left)
                {
                    ((BinaryTreeNode<T>) x.Parent)._Left = y;
                }
                else
                {
                    ((BinaryTreeNode<T>) x.Parent)._Right = y;
                }
            }
            else
            {
                _Root = y;
            }

            y._Left = x;
            if (x != _sentinel)
            {
                x.Parent = y;
            }
        }

        private void RotateRight(BinaryTreeNode<T> x)
        {
            BinaryTreeNode<T> y = x._Left;

            x._Left = y._Right;
            if (y._Right != _sentinel && y._Right != null)
            {
                y._Right.Parent = x;
            }

            if (y != _sentinel)
            {
                y.Parent = x.Parent;
            }

            if (x.Parent != null && x.Parent != _sentinel)
            {
                if (x == ((BinaryTreeNode<T>) x.Parent)._Right)
                {
                    ((BinaryTreeNode<T>) x.Parent)._Right = y;
                }
                else
                {
                    ((BinaryTreeNode<T>) x.Parent)._Left = y;
                }
            }
            else
            {
                _Root = y;
            }

            y._Right = x;
            if (x != _sentinel)
            {
                x.Parent = y;
            }
        }

        private void InsertFixup(BinaryTreeNode<T> x)
        {
            while (x != _Root && ((BinaryTreeNode<T>) x.Parent)._Color == NodeColor.Red && x.Parent.Parent != null)
            {
                if (x.Parent == ((BinaryTreeNode<T>) x.Parent.Parent)._Left)
                {
                    BinaryTreeNode<T> y = ((BinaryTreeNode<T>) x.Parent.Parent)._Right;
                    if (y._Color == NodeColor.Red)
                    {
                        ((BinaryTreeNode<T>) x.Parent)._Color = NodeColor.Black;
                        y._Color = NodeColor.Black;
                        ((BinaryTreeNode<T>) x.Parent.Parent)._Color = NodeColor.Red;
                        x = ((BinaryTreeNode<T>) x.Parent.Parent);
                    }
                    else
                    {
                        if (x == ((BinaryTreeNode<T>) x.Parent)._Right)
                        {
                            x = ((BinaryTreeNode<T>) x.Parent);
                            RotateLeft(x);
                        }

                        ((BinaryTreeNode<T>) x.Parent)._Color = NodeColor.Black;
                        ((BinaryTreeNode<T>) x.Parent.Parent)._Color = NodeColor.Red;
                        RotateRight(((BinaryTreeNode<T>) x.Parent.Parent));
                    }
                }
                else
                {
                    BinaryTreeNode<T> y = ((BinaryTreeNode<T>) x.Parent.Parent)._Left;
                    if (y._Color == NodeColor.Red)
                    {
                        ((BinaryTreeNode<T>) x.Parent)._Color = NodeColor.Black;
                        y._Color = NodeColor.Black;
                        ((BinaryTreeNode<T>) x.Parent.Parent)._Color = NodeColor.Red;
                        x = ((BinaryTreeNode<T>) x.Parent.Parent);
                    }
                    else
                    {
                        if (x == ((BinaryTreeNode<T>) x.Parent)._Left)
                        {
                            x = ((BinaryTreeNode<T>) x.Parent);
                            RotateRight(x);
                        }
                        ((BinaryTreeNode<T>) x.Parent)._Color = NodeColor.Black;
                        ((BinaryTreeNode<T>) x.Parent.Parent)._Color = NodeColor.Red;
                        RotateLeft(((BinaryTreeNode<T>) x.Parent.Parent));
                    }
                }
            }

            if (_Root != null) _Root._Color = NodeColor.Black;
        }

        private void DeleteFixup(BinaryTreeNode<T> x)
        {
            while (x != _Root && x != null && x._Color == NodeColor.Black)
            {
                if (x == ((BinaryTreeNode<T>) x.Parent)._Left)
                {
                    BinaryTreeNode<T> w = ((BinaryTreeNode<T>) x.Parent)._Right;
                    if (w._Color == NodeColor.Red)
                    {
                        w._Color = NodeColor.Black;
                        ((BinaryTreeNode<T>) x.Parent)._Color = NodeColor.Red;
                        RotateLeft(((BinaryTreeNode<T>) x.Parent));
                        w = ((BinaryTreeNode<T>) x.Parent)._Right;
                    }
                    if (w._Left._Color == NodeColor.Black && w._Right._Color == NodeColor.Black)
                    {
                        w._Color = NodeColor.Red;
                        x = ((BinaryTreeNode<T>) x.Parent);
                    }
                    else
                    {
                        if (w._Right._Color == NodeColor.Black)
                        {
                            w._Left._Color = NodeColor.Black;
                            w._Color = NodeColor.Red;
                            RotateRight(w);
                            w = ((BinaryTreeNode<T>) x.Parent)._Right;
                        }
                        w._Color = ((BinaryTreeNode<T>) x.Parent)._Color;
                        ((BinaryTreeNode<T>) x.Parent)._Color = NodeColor.Black;
                        w._Right._Color = NodeColor.Black;
                        RotateLeft(((BinaryTreeNode<T>) x.Parent));
                        x = _Root;
                    }
                }
                else
                {
                    BinaryTreeNode<T> w = ((BinaryTreeNode<T>) x.Parent)._Left;
                    if (w != null)
                    {
                        if (w._Color == NodeColor.Red)
                        {
                            w._Color = NodeColor.Black;
                            ((BinaryTreeNode<T>) x.Parent)._Color = NodeColor.Red;
                            RotateRight(((BinaryTreeNode<T>) x.Parent));
                            w = ((BinaryTreeNode<T>) x.Parent)._Left;
                        }
                        if (w != null)
                        {
                            if (w._Right._Color == NodeColor.Black && w._Left._Color == NodeColor.Black)
                            {
                                w._Color = NodeColor.Red;
                                x = ((BinaryTreeNode<T>) x.Parent);
                            }
                            else
                            {
                                if (w._Left._Color == NodeColor.Black)
                                {
                                    w._Right._Color = NodeColor.Black;
                                    w._Color = NodeColor.Red;
                                    RotateLeft(w);
                                    w = ((BinaryTreeNode<T>) x.Parent)._Left;
                                }
                                if (w != null) w._Color = ((BinaryTreeNode<T>) x.Parent)._Color;
                                ((BinaryTreeNode<T>) x.Parent)._Color = NodeColor.Black;
                                if (w != null) w._Left._Color = NodeColor.Black;
                                RotateRight(((BinaryTreeNode<T>) x.Parent));
                                x = _Root;
                            }
                        }
                    }
                }
            }

            if (x != null) x._Color = NodeColor.Black;
        }
    }
}